package week_four;

public class FindMinimumInRotatedSortedArrayII_154 {
    public int findMin(int[] nums) {
        // 3种情况，nums[mid]==nums[r]，不能确定舍弃哪边，所以r--，继续。
        //nums[mid] < nums[r], 舍弃右边，r=mid
        //nums[mid] > nums[r], 舍弃左边 l=mid+1

        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] < nums[r]) {
                r = mid;
            } else if (nums[mid] > nums[r]) {
                l = mid + 1;
            } else
                r--;
        }
        return nums[r];
    }
}
